package com.leetcode.partition17;

import com.leetcode.common.TreeNode;

import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/12/25 10:35
 */
@SuppressWarnings("all")
public class LC1609奇偶树 {

    private static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(4, new TreeNode(3), new TreeNode(3)),
                new TreeNode(2, new TreeNode(7), null));
        System.out.println(isEvenOddTree(root));
    }

    public static boolean isEvenOddTree(TreeNode root) {
        int level = 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size(), prev = (level & 1) == 0 ? -INF : INF;
            for (int i = 0; i < size; i++) {
                //如果是偶数层，所有的节点需要是奇数且单调递增；如果是奇数层，所有节点需要是偶数且单调递减
                TreeNode curr = queue.pollFirst();
                if ((level & 1) == 0) {
                    if ((curr.val & 1) == 0 || prev >= curr.val) return false;
                    prev = curr.val;
                } else {
                    if ((curr.val & 1) == 1 || prev <= curr.val) return false;
                    prev = curr.val;
                }
                if (curr.left != null) queue.addLast(curr.left);
                if (curr.right != null) queue.addLast(curr.right);
            }
            level++;
        }
        return true;
    }
}
